<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xml:lang="en" lang="en">
<!-- Created by GNU Texinfo 5.1, http://www.gnu.org/software/texinfo/ -->
<head>
<title>Structure and Interpretation of Computer Programs, 2e: Chapter 5</title>

<meta name="description" content="Structure and Interpretation of Computer Programs, 2e: Chapter 5" />
<meta name="keywords" content="Structure and Interpretation of Computer Programs, 2e: Chapter 5" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<meta name="Generator" content="texi2any" />
<meta charset="utf-8" />
<link href="index.xhtml#Top" rel="start" title="Top" />
<link href="Term-Index.xhtml#Term-Index" rel="index" title="Term Index" />
<link href="index.xhtml#SEC_Contents" rel="contents" title="Table of Contents" />
<link href="index.xhtml#Top" rel="prev" title="Top" />
<link href="5_002e1.xhtml#g_t5_002e1" rel="next" title="5.1" />
<link href="4_002e4.xhtml#g_t4_002e4_002e4_002e8" rel="prev" title="4.4.4.8" />

<link href="css/style.css" rel="stylesheet" type="text/css" />
<link href="css/prettify.css" rel="stylesheet" type="text/css" />
</head>

<body>
<section><span class="top jump" title="Jump to top"><a href="#pagetop" accesskey="t">⇡</a></span><a id="pagetop"></a><a id="Chapter-5"></a>
<nav class="header">
<p>
Next: <a href="5_002e1.xhtml#g_t5_002e1" accesskey="n" rel="next">5.1</a>, Prev: <a href="4_002e4.xhtml#g_t4_002e4" accesskey="p" rel="prev">4.4</a>, Up: <a href="index.xhtml#Top" accesskey="u" rel="prev">Top</a>   [<a href="index.xhtml#SEC_Contents" title="Table of contents" accesskey="c" rel="contents">Contents</a>]</p>
</nav>
<a id="Computing-with-Register-Machines"></a>
<h2 class="chapter"><span class="chapnum">5</span><span class="chaptitle">Computing with Register Machines</span></h2>

<blockquote>
<p>My aim is to show that the heavenly machine is not a kind of divine, live
being, but a kind of clockwork (and he who believes that a clock has soul
attributes the maker’s glory to the work), insofar as nearly all the manifold
motions are caused by a most simple and material force, just as all motions of
the clock are caused by a single weight.
</p>
<p>—Johannes Kepler (letter to Herwart von Hohenburg, 1605)
</p></blockquote>


<p>We began this book by studying processes and by describing processes in terms
of procedures written in Lisp.  To explain the meanings of these procedures, we
used a succession of models of evaluation: the substitution model of
<a href="Chapter-1.xhtml#Chapter-1">Chapter 1</a>, the environment model of <a href="Chapter-3.xhtml#Chapter-3">Chapter 3</a>, and the metacircular
evaluator of <a href="Chapter-4.xhtml#Chapter-4">Chapter 4</a>.  Our examination of the metacircular evaluator,
in particular, dispelled much of the mystery of how Lisp-like languages are
interpreted.  But even the metacircular evaluator leaves important questions
unanswered, because it fails to elucidate the mechanisms of control in a Lisp
system.  For instance, the evaluator does not explain how the evaluation of a
subexpression manages to return a value to the expression that uses this value,
nor does the evaluator explain how some recursive procedures generate iterative
processes (that is, are evaluated using constant space) whereas other recursive
procedures generate recursive processes.  These questions remain unanswered
because the metacircular evaluator is itself a Lisp program and hence inherits
the control structure of the underlying Lisp system.  In order to provide a
more complete description of the control structure of the Lisp evaluator, we
must work at a more primitive level than Lisp itself.
</p>
<p>In this chapter we will describe processes in terms of the step-by-step
operation of a traditional computer.  Such a computer, or <a id="index-register-machine"></a>
<em>register machine</em>, 
sequentially executes <a id="index-instructions"></a>
<em>instructions</em> that manipulate the
contents of a fixed set of storage elements called <a id="index-registers"></a>
<em>registers</em>.  A
typical register-machine instruction applies a primitive operation to the
contents of some registers and assigns the result to another register.  Our
descriptions of processes executed by register machines will look very much
like “machine-language” programs for traditional computers.  However, instead
of focusing on the machine language of any particular computer, we will examine
several Lisp procedures and design a specific register machine to execute each
procedure.  Thus, we will approach our task from the perspective of a hardware
architect rather than that of a machine-language computer programmer.  In
designing register machines, we will develop mechanisms for implementing
important programming constructs such as recursion.  We will also present a
language for describing designs for register machines.  In <a href="5_002e2.xhtml#g_t5_002e2">5.2</a> we
will implement a Lisp program that uses these descriptions to simulate the
machines we design.
</p>
<p>Most of the primitive operations of our register machines are very simple.  For
example, an operation might add the numbers fetched from two registers,
producing a result to be stored into a third register.  Such an operation can
be performed by easily described hardware.  In order to deal with list
structure, however, we will also use the memory operations <code>car</code>,
<code>cdr</code>, and <code>cons</code>, which require an elaborate storage-allocation
mechanism.  In <a href="5_002e3.xhtml#g_t5_002e3">5.3</a> we study their implementation in terms of more
elementary operations.
</p>
<p>In <a href="5_002e4.xhtml#g_t5_002e4">5.4</a>, after we have accumulated experience formulating simple
procedures as register machines, we will design a machine that carries out the
algorithm described by the metacircular evaluator of <a href="4_002e1.xhtml#g_t4_002e1">4.1</a>.  This
will fill in the gap in our understanding of how Scheme expressions are
interpreted, by providing an explicit model for the mechanisms of control in
the evaluator.  In <a href="5_002e5.xhtml#g_t5_002e5">5.5</a> we will study a simple compiler that
translates Scheme programs into sequences of instructions that can be executed
directly with the registers and operations of the evaluator register machine.
</p>

<nav class="header">
<p>
Next: <a href="5_002e1.xhtml#g_t5_002e1" accesskey="n" rel="next">5.1</a>, Prev: <a href="4_002e4.xhtml#g_t4_002e4" accesskey="p" rel="prev">4.4</a>, Up: <a href="index.xhtml#Top" accesskey="u" rel="prev">Top</a>   [<a href="index.xhtml#SEC_Contents" title="Table of contents" accesskey="c" rel="contents">Contents</a>]</p>
</nav>


</section><span class="bottom jump" title="Jump to bottom"><a href="#pagebottom" accesskey="b">⇣</a></span><a id="pagebottom"></a>
</body>
</html>